package main

import "fmt"

/**
 * 插入排序
 */
func insertionSort(a []int) []int {
	// [3,5,6,8][1,8,0,3,9,2]
	//        |  |
	//        j  i
	for i := 0; i < len(a); i++ {
		e := a[i]
		j := i - 1
		for j >= 0 {
			if e < a[j] {
				a[j+1] = a[j]
			} else {
				break
			}
			j--
		}
		a[j+1] = e
	}
	return a
}

func main() {
	a := [...]int{8, 6, 10, 7, 9, 3, 4, 5, 2, 1}

	fmt.Printf("a = %v\n", a)

	insertionSort(a[:5])
	insertionSort(a[5:])
	fmt.Println()

	fmt.Printf("a = %v\n", a)
}
